package com.btc.study.sort;

import java.util.Arrays;

/**
 * @Auther: hq
 * @Description: 插入排序
 * @Date 2019/6/24 11:23
 */
public class InsertionSort {

    public static int[] insertionSort(int[] a, int n){
        if (n <= 1){
            return a;
        }
        for(int i = 1 ; i < n; i++){
            int value = a[i];
            int j = i -1;
            for(; j >= 0 ; j-- ){
                if(a[j] > value){
                    a[j + 1] = a[j];
                }else {
                    break;
                }
            }
            a[j + 1] = value;
            System.out.println(Arrays.toString(a));
        }
        return a;
    }

    
    public static void main(String[] args){
        int a[] = {4,2,3,1,5,1};
        System.out.println("============ insertionSort ============");
        insertionSort(a, 6);
    }
    
    
    
}
